package com.yvon.service.demo.algorithm.offer;

/**
 * @author : Yvon
 * @since : 2022-07-26
 */
public class P19 {
    public static void main(String[] args) {
        Solution solution = new P19().new Solution();
        String s = "bbdccd";
        String p = "a*bb.c*e*d";

        boolean aabbccd = solution.isMatch(s, p);
        System.out.println(aabbccd);

    }

    class Solution {
        public boolean isMatch(String s, String p) {
            if (p.isEmpty()) {
                return s.isEmpty();
            }
            boolean firstMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0)|| p.charAt(0) == '.');
            if (p.length() >= 2 && p.charAt(1) == '*') {
                // p的第i个元素在s中出现0次: 此时，我们保持s不变，将p剪2个元素，继续调用isMatch。如：s=‘bb’,p='a*bb'，将p的首部2个元素剪去，得到p=‘bb’,继续比较；
                // p的第i个元在s中出现一次或者多次: 此时，比较i元素与s的首元素，如果相同，剪去s的首元素，保持p不变继续调用isMatch。如：s=‘aabb’,p='a*bb',那么比较首元素相同，再剪去s首元素得s=‘abb’，在调用isMatch比较。
                return isMatch(s, p.substring(2)) || (firstMatch && isMatch(s.substring(1), p));
            }else {
                return firstMatch && isMatch(s.substring(1), p.substring(1));
            }
        }
    }
}
